package com.algorithm.base.backtracking;

import java.util.*;

/**
 * 131. 分割回文串
 * 可用动态规划优化
 *
 * @author Amadeus
 * @date 2023/11/02
 */
public class Partition {

    List<List<String>> result = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();

    /**
     * 分割回文串
     *
     * @param s s
     * @return {@link List}<{@link List}<{@link String}>>
     */
    public List<List<String>> partition(String s) {
        backTracking(0, s);
        return result;
    }

    public void backTracking(int index, String s) {
        if (index >= s.length()) {
            result.add(new ArrayList<>(deque));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (checkKmp(index, i, s)) {
                deque.addLast(s.substring(index, i + 1));
            } else {
                continue;
            }
            backTracking(i + 1, s);
            deque.removeLast();
        }
    }

    public boolean checkKmp(int index, int j, String s) {
        while (index < j) {
            if (s.charAt(index) != s.charAt(j)) {
                return false;
            }
            index++;
            j--;
        }
        return true;
    }
}
